package com.leaves.leetcode.array.t16_3SumClosest;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


/**
 * 核心要点：
 * 1、排序加双指针
 * 2、这个用4那种先外层遍历左指针方式很不方便，而且效率不高，因为需要考虑当前左指针对应情况下，最优得右指针后才能移动左指针这个会让时间复杂度上升，不如同时移动，每次移动到新得数对后进行判断
 * **3、这里比较重要的3个点是下面的三个优化，同时防止数组越界，first最大只能到n-3
 */
class Solution {

    /**
     * 排序+双指针+剪枝
     * 1、为了不挑选到相同位置的数，使用3层for循环
     * 2、为了不选到重复的数字对，考虑对原数组进行排列
     * 3、对于a+b+c=0若固定了a，b和c就是一增一降的关系，对于这种关系可以考虑双指针
     * 4、双指针不一定就要左右同时移动，可以像该官方的方式，先外层遍历左指针，跳过重复的元素，在内存遍历右指针(这里对于右指针的遍历，跳过不符合公式的方式更优于跳过重复元素，因为可能有一连串不符合公式的数字串但并不重复，这样可以一次性过滤掉，无需再次进入外层循环)
     * 5、针对第4点，左右指针肯定都是要遍历到left==right的位置的，一种是外层遍历left内层遍历right，一种是外层只遍历left和right关系，left和right的遍历放在内层。这两种都行，第一种逻辑比较清晰
     *
     * 6、这个用4那种先外层遍历左指针方式很不方便，而且效率不高，因为需要考虑当前左指针对应情况下，最优得右指针后才能移动左指针这个会让时间复杂度上升，不如同时移动，每次移动到新得数对后进行判断
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(nlogn) 排序空间
     * @param nums
     * @return
     */
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        int best = 10000000;

        // 枚举 a
        for (int i = 0; i < n-2; ++i) {
            // 优化一： 保证和上一次枚举的元素不相等
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            // 优化二： 若nums[i] + nums[i+1] + nums[i+2] > target 那么后续已经无需再遍历了，因为都比当前3数和要大
            int preJudgeNum = nums[i] + nums[i+1] + nums[i+2];
            if (preJudgeNum >= target) {
                if (Math.abs(best - target) > preJudgeNum - target) best = preJudgeNum;
                break;
            }

            // 优化二： 若nums[i] + nums[n-2] + nums[n-1] < target 那么可以遍历下一个first位置了，因为当前first位置最大的数也小于target，后序遍历second和third就没意义了
            preJudgeNum = nums[i] + nums[n-2] + nums[n-1];
            if (preJudgeNum <= target) {
                if (Math.abs(best - target) > preJudgeNum - target) best = preJudgeNum;
                if (preJudgeNum == target) break;
                continue;
            }


            // 使用双指针枚举 b 和 c
            int j = i + 1, k = n - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                // 如果和为 target 直接返回答案
                if (sum == target) {
                    return target;
                }
                // 根据差值的绝对值来更新答案
                if (Math.abs(sum - target) < Math.abs(best - target)) {
                    best = sum;
                }
                if (sum > target) {
                    // 如果和大于 target，移动 c 对应的指针
                    int k0 = k - 1;
                    // 移动到下一个不相等的元素
                    while (j < k0 && nums[k0] == nums[k]) {
                        --k0;
                    }
                    k = k0;
                } else {
                    // 如果和小于 target，移动 b 对应的指针
                    int j0 = j + 1;
                    // 移动到下一个不相等的元素
                    while (j0 < k && nums[j0] == nums[j]) {
                        ++j0;
                    }
                    j = j0;
                }
            }
        }
        return best;
    }

}